﻿// owner 蒋家伟

#include "PrefixTree.h"

// std
#include <functional>

#include "Dbg_Warn_Define.h"

using namespace jsdk;

OwnerPtr<jsdk::PrefixTreeNode> jsdk::PrefixTreeNode::create(wchar_t wchar)
{
    DBG_WARN_AND_RETURN_NULLPTR_UNLESS(wchar != L'\0', L"传入了 ‘\0’ 作为匹配字符节点", L"蒋家伟", L"2023-09-13");
    return NEW_AS_OWNERPTR(jsdk::PrefixTreeNode, wchar);
}

void jsdk::PrefixTreeNode::subtractPasscount()
{
    DBG_WARN_AND_RETURN_VOID_UNLESS(m_passCount > 0, L"通过的数量已经为0，当前节点应该不存在，无法继续减1", L"蒋家伟", L"2023-09-13");
    m_passCount--;
}

PrefixTreeNode* jsdk::PrefixTreeNode::findfw(wchar_t wchar)
{
    auto& iter = m_childrenNodes.find(wchar);
    if (iter != m_childrenNodes.end())
    {
        return iter->second.get();
    }
    return nullptr;
}

const jsdk::PrefixTreeNode* jsdk::PrefixTreeNode::find(wchar_t wchar) const
{
    const auto& iter = m_childrenNodes.find(wchar);
    if (iter != m_childrenNodes.end())
    {
        return iter->second.get();
    }
    return nullptr;
}

bool jsdk::PrefixTreeNode::addChildrenNode(OwnerPtr<PrefixTreeNode> opPrefixTreeNode)
{
    DBG_WARN_AND_RETURN_FALSE_UNLESS(opPrefixTreeNode, L"添加的子节点为空", L"蒋家伟", L"2023-09-13");
    PrefixTreeNode* pPrefixTreeNode = opPrefixTreeNode.get();
    if (m_childrenNodes.insert(std::make_pair(pPrefixTreeNode->getchar(), std::move(opPrefixTreeNode))).second)
    {
        pPrefixTreeNode->setParent(this);
        return true;
    }
    return false;
}

std::wstring jsdk::PrefixTreeNode::getString() const
{
    std::wstring str;
    const jsdk::PrefixTreeNode* pTempTreeNode = this;
    while (pTempTreeNode)
    {
        if (pTempTreeNode->m_childrenNodes.size() > 0)
        {
            str += pTempTreeNode->m_childrenNodes.begin()->first;
            pTempTreeNode = pTempTreeNode->m_childrenNodes.begin()->second.get();
        }
        else
        {
            DBG_WARN_AND_RETURN_UNLESS(pTempTreeNode->isEnd(), str, L"当前节点没有子节点，应该为end", L"蒋家伟", L"2023-09-13");
            return str;
        }
    }

    return str;
}

jsdk::PrefixTreeNode::PrefixTreeNode(wchar_t wchar): m_char(wchar)
{
}

std::wstring jsdk::PrefixTree::getPrefixString(const PrefixTreeNode* pPrefixTreeNode)
{
    std::wstring str;
    while (pPrefixTreeNode)
    {
        if (pPrefixTreeNode->getParent() == nullptr)
        {
            // 如果当前节点没有根节点则直接返回，解决根节点无数据的情况
            return str;
        }
        str = pPrefixTreeNode->getchar() + str;
        pPrefixTreeNode = pPrefixTreeNode->getParent();
    }
    return str;
}

std::wstring jsdk::PrefixTree::getPrefixString2(const PrefixTreeNode* pPrefixTreeNode)
{
    const PrefixTreeNode* ptemp = pPrefixTreeNode;
    return getPrefixString(pPrefixTreeNode) + ptemp->getString();
}

OwnerPtr<jsdk::PrefixTree> jsdk::PrefixTree::create()
{
    OwnerPtr<jsdk::PrefixTree> opPrefixTree = NEW_AS_OWNERPTR(jsdk::PrefixTree);
    DBG_WARN_AND_RETURN_NULLPTR_UNLESS(opPrefixTree, L"前缀树创建失败", L"蒋家伟", L"2023-09-13");
    return opPrefixTree->m_opRootNode ? std::move(opPrefixTree) : nullptr;
}

bool jsdk::PrefixTree::addPrefix(const std::wstring& prefixStr, std::wstring& errorMsg)
{
    std::function<void(PrefixTreeNode*)> deleteTreeNode = [&deleteTreeNode](PrefixTreeNode* pCurrentNode) {
        if (PrefixTreeNode* pParentNode = pCurrentNode->getParent())
        {
            pParentNode->subtractPasscount();
            deleteTreeNode(pParentNode);
        }
    };

    DBG_WARN_AND_RETURN_FALSE_UNLESS(m_opRootNode, L"根节点未初始化", L"蒋家伟", L"2023-09-13");
    // 设置一个当前节点
    PrefixTreeNode* pCurrentNode = m_opRootNode.get();
    for (int i=0; i< prefixStr.size(); i++)
    {
        DBG_WARN_AND_RETURN_FALSE_UNLESS(pCurrentNode, L"当前节点为空", L"蒋家伟", L"2023-09-13");
        pCurrentNode->addPasscount(); // 会经过当前路径一次
        jsdk::PrefixTreeNode* pChildrenTreeNodes = pCurrentNode->findfw(prefixStr[i]);
        if (pChildrenTreeNodes)
        {
            if (pChildrenTreeNodes->isEnd())
            {
                // 如果存在以当前节点为结束的前缀，说明出现了冲突
                errorMsg = L"添加的前缀包含了已缓存的前缀，添加的前缀 : " + prefixStr + L"缓存前缀 : " + getPrefixString(pChildrenTreeNodes);
                deleteTreeNode(pChildrenTreeNodes);
                return false;
            }
            pCurrentNode = pChildrenTreeNodes;
        }
        else
        {
            // 没找到则创建一个
            OwnerPtr<PrefixTreeNode> opPrefixTreeNode = PrefixTreeNode::create(prefixStr[i]);
            DBG_WARN_AND_RETURN_FALSE_UNLESS(opPrefixTreeNode, std::wstring(L"子节点创建失败 : ") + prefixStr[i], L"蒋家伟", L"2023-09-13");
            PrefixTreeNode* pTempNode = opPrefixTreeNode.get();
            pCurrentNode->addChildrenNode(std::move(opPrefixTreeNode));             // 将这个节点作为当前节点的子节点
            pCurrentNode = pTempNode;                                               // 将节点传递下去
        }

        if (i == prefixStr.size() - 1)
        {
            if (pCurrentNode->getPassCount() > 0)
            {
                // 说明当前字符串成为其他前缀的子串
                errorMsg = L"添加的前缀为缓存前缀的子串, 添加前缀 : " + prefixStr + L"缓存前缀 : " + getPrefixString2(pChildrenTreeNodes);
                deleteTreeNode(pCurrentNode);
                return false;
            }
            // 已经到了最后一个位置， 将目标节点设置为终止节点
            pCurrentNode->setisEnd(true);
            pCurrentNode->addPasscount();
        }
    }
    return true;
}

std::vector<std::pair<uint32_t, uint32_t>> jsdk::PrefixTree::match(const std::wstring& matchStr) const
{
    // 时间复杂度是线性的最好为On，最差O(n*m) m是所有缓存字符串中最长的字符串长度。对于匹配缓存的个数无影响
    std::vector<std::pair<uint32_t, uint32_t>> res;
    DBG_WARN_AND_RETURN_UNLESS(m_opRootNode, res, L"根节点未初始化", L"蒋家伟", L"2023-09-13");
    // 为了算法简便性，在结尾补零
    std::wstring matchedStr = matchStr + L'\0';
    for (int i = 0; i < matchedStr.size();)
    {
        if (const PrefixTreeNode* pTreeNode = m_opRootNode->find(matchedStr[i]))
        {
            if (pTreeNode->isEnd())
            {
                // 如果当前找到节点已经结束了，则表示缓存的前缀只有一个字符，查找成功
                res.push_back(std::make_pair(i, 1));
                i += 1;
                continue;
            }
            else
            {
                // 找到一个节点
                int j = i + 1;
                for (; j < matchedStr.size(); j++)
                {
                    if (pTreeNode = pTreeNode->find(matchedStr[j]))
                    {
                        // 说明找到了一个子节点，则继续匹配下一个字符
                        if (pTreeNode->isEnd())
                        {
                            // 如果查找的节点为末尾节点，则表示匹配成功
                            res.push_back(std::make_pair(i, j-i + 1));
                            i = j + 1;
                            break;
                        }
                    }
                    else
                    {
                        // 整串匹配失败，回归到最初的起点
                        i += 1;
                        break;
                    }
                }
            }
        }
        else
        {
            // 当前字符没有缓存
            i += 1;
            continue;
        }
    }
    return res;
}

void jsdk::PrefixTree::swap(OwnerPtr<IPrefixTree>& opPrefixTree)
{
    PrefixTree* pPrefixTree = dynamic_cast<PrefixTree*>(opPrefixTree.get());
    DBG_WARN_AND_RETURN_VOID_UNLESS(pPrefixTree, L"当前传递的前缀树不是PrefixTree", L"蒋家伟", L"2023-09-13");
    this->m_opRootNode.swap(pPrefixTree->m_opRootNode);
}

uint32_t jsdk::PrefixTree::getPrefixCount() const
{
    DBG_WARN_AND_RETURN_UNLESS(m_opRootNode, 0, L"根节点未初始化", L"蒋家伟", L"2023-09-13");
    return m_opRootNode->getPassCount();
}

std::vector<std::wstring> jsdk::PrefixTree::getPrefixStr() const
{
    std::vector<std::wstring> res;
    DBG_WARN_AND_RETURN_UNLESS(m_opRootNode, res, L"根节点未初始化", L"蒋家伟", L"2023-09-13");
    // 设置一个当前节点
    std::function<void(const PrefixTreeNode*, std::wstring&)> fun = [&fun, &res](const PrefixTreeNode* pCurrentNode, std::wstring& prefixStr) {
        if (pCurrentNode == nullptr)
            return;

        if (pCurrentNode->isEnd())
        {
            DBG_WARN_AND_RETURN_VOID_UNLESS(pCurrentNode->getPassCount() == 1 && pCurrentNode->getChildrenNodeSize() == 0, L"前缀树的节点为End，节点通过数不为1或者存在子节点，请联系实现人员检查内部算法是否实现有误", L"蒋家伟", L"2023-10-23");
            res.push_back(prefixStr);
            return;
        }

        for (const auto& iter : pCurrentNode->getChildrenNodes())
        {
            DBG_WARN_AND_CONTINUE_UNLESS(iter.second, L"子节点为空指针", L"蒋家伟", L"2023-10-23");
            prefixStr.push_back(iter.second->getchar());
            fun(iter.second.get(), prefixStr);
            prefixStr.pop_back();
        }
    };

    std::wstring tempStr;
    fun(m_opRootNode.get(), tempStr);
    DBG_WARN_AND_RETURN_UNLESS(res.size() == getPrefixCount(), std::vector<std::wstring>{}, L"获取的前缀个数不等于根节点通过的元素个数, 请联系算法实现人员查看内部实现是否存在异常", L"蒋家伟", L"2023-10-13");

    return res;
}

jsdk::PrefixTree::PrefixTree():
    m_opRootNode(NEW_AS_OWNERPTR(jsdk::PrefixTreeNode, L'\0'))
{
}
